#include <stdio.h>
#include <malloc.h>
#define FALSE 0
#define TRUE 1
#define OK 1
#define ERROR -1
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct Lnode
{
    ElemType data;
    Lnode* next;
}Lnode, *LinkList;
Status InitList(LinkList &L)
{
    L = (LinkList)malloc(sizeof(Lnode));
    if (!L)
        return OVERFLOW;
    L->data = 0;
    L->next = NULL;
    return OK;
}
Status DestroyList(LinkList &L)
{
    LinkList cur = L, pre;
    while (cur)
    {
        pre = cur;
        cur = cur->next;
        free(pre);
    }
    return OK;
}
Status ClearList(LinkList &L)
{
    LinkList cur = L->next, pre;
    while (cur)
    {
        pre = cur;
        cur = cur->next;
        free(pre);
    }
    L->data = 0;
    L->next = NULL;
    return OK;
}
Status ListEmpty(LinkList L)
{
    if (L->next)
        return FALSE;
    return TRUE;
}
int ListLength(LinkList L)
{
    return L->data;
}
Status GetElem(LinkList L, int i, ElemType &e)
{
    LinkList p = L;
    if (i < 1 || i > p->data)
        return ERROR;
    while (i--)
        p = p->next;
    e = p->data;
    return OK;
}
int LocateElem(LinkList L, ElemType e, bool (*compare)(ElemType, ElemType))
{
    LinkList p = L->next;
    int loc = 1;
    while (p)
    {
        if (!compare(e, p->data))
            return loc;
        p = p->next;
        ++loc;
    }
    return -1;
}
Status PriorElem(LinkList L, ElemType cur_e, ElemType &pre_e)
{
    LinkList pre = L->next, cur = L->next->next;
    while (cur)
    {
        if (cur_e == cur->data)
        {
            pre_e = pre->data;
            return OK;
        }
        pre = cur;
        cur = cur->next;
    }
    return ERROR;
}
Status NextElem(LinkList L, ElemType cur_e, ElemType &next_e)
{
    LinkList p = L->next;
    while (p->next)
    {
        if (p->data == cur_e)
        {
            next_e = p->next->data;
            return OK;
        }
        p = p->next;
    }
    return ERROR;
}
Status ListInsert(LinkList &L, int i, ElemType e)
{
    if (i < 1 || i > L->data + 1)
        return ERROR;
    LinkList p = L;
    --i;
    while (i--)
        p = p->next;
    LinkList newspace = (LinkList)malloc(sizeof(Lnode));
    if (!newspace)
        return OVERFLOW;
    newspace->data = e;
    newspace->next = p->next;
    p->next = newspace;
    ++L->data;
    return OK;
}
Status ListDelete(LinkList &L, int i, ElemType &e)
{
    if (i < 1 || i > L->data)
        return ERROR;
    LinkList p = L;
    --i;
    while (i--)
        p = p->next;
    LinkList m = p->next;
    p->next = p->next->next;
    free(m);
    --L->data;
    return OK;
}
Status ListTraverse(LinkList L, Status (*visit)(ElemType))
{
    printf("len = %d\n", ListLength(L));
    L = L->next;
    while (L)
    {
        if (!visit(L->data))
            return ERROR;
        L = L->next;
    }
    printf("\n");
    return OK;
}
Status visit(ElemType e)
{
    printf("%3d", e);
    return OK;
}
bool compare(ElemType a, ElemType b)
{
    return a-b;
}
int main(void)
{
    LinkList L;
    InitList(L);
    
    ListTraverse(L, visit);

    for (int i = 1; i < 5; ++i)
        ListInsert(L, i, 2*i);
    
    ListTraverse(L, visit);

    // ClearList(L);
    // ListTraverse(L, visit);

    ElemType e;
    int loc = 2;
    GetElem(L, loc, e);
    printf("loc = %d, e = %d\n", loc, e);
    ElemType cur_e = 6, pre_e, next_e;
    PriorElem(L, 6, pre_e);
    printf("cur_e = %d, pre_e = %d\n", cur_e, pre_e);
    NextElem(L, cur_e, next_e);
    printf("cur_e = %d, next_e = %d\n", cur_e, next_e);

    ListDelete(L, 4, e);
    printf("del_elem = %d\n", e);
    ListTraverse(L, visit);
    
    printf("2 is locate at pos%d", LocateElem(L, 2, compare));

    return 0;
}